package pack;

import java.util.Arrays;

/**
 * @Author Elephas
 * @Date 2022/4/28
 **/
@FunctionalInterface
public interface OneZeroPack {
    /**
     * 0-1 背包问题，将N件物品放入重量容量为V的包裹，第i件物品的价值为C[i],重量为W[i],使得背包内总价值最大
     * @param N         物品数量
     * @param V         背包容量
     * @param C         物品重量
     * @param W         物品价值
     * @return          最大可获得价值
     */
    int oneZeroPack(int N, int V, int[] C, int[] W);
}
class OneZeroPackTest{
    static final String TEST_01 = "3,4,1,4,3,2,4,3";

    public static void main(String[] args) {
        // 解析测试用例
        String[] tokens = TEST_01.split(",");
        int N = Integer.parseInt(tokens[0]);
        int V = Integer.parseInt(tokens[1]);

        int[] Costs = new int[N];
        int[] Weights = new int[N];
        for(int i = 0; i < N; i++){
            Costs[i] = Integer.parseInt(tokens[2 + i]);
        }
        for(int i = 0; i < N; i++){
            Weights[i] = Integer.parseInt(tokens[2 + N + i]);
        }

        // 调用方法
        int maxValue = new OneZeroPackImpl3().oneZeroPack(N, V, Costs, Weights);

        System.out.println(maxValue);

        return;
    }
}

class OneZeroPackImpl1 implements OneZeroPack{

    @Override
    public int oneZeroPack(int N, int V, int[] C, int[] W) {
        int[][] dp = new int[N + 1][V + 1];
        Arrays.fill(dp[0], 0);
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= V; j++){
                // dp[i][v] = max{dp[i - 1][v], W[i] + dp[i - 1][v - C[i]]}
                if(C[i - 1] <= j){
                    int cost1 = dp[i - 1][j];
                    int cost2 = dp[i - 1][j - C[i - 1]] + W[i - 1];
                    dp[i][j] = cost1 > cost2 ? cost1 : cost2;
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N][V];
    }
}
class OneZeroPackImpl2 implements OneZeroPack{

    @Override
    public int oneZeroPack(int N, int V, int[] C, int[] W) {
        int[] dp = new int[V + 1];
        Arrays.fill(dp, 0);
        for(int i = 1; i <= N; i++){
            for(int j = V; j > 0; j--){
                if(C[i - 1] <= j){
                    int cost1 = dp[j];
                    int cost2 = dp[j - C[i - 1]] + W[i - 1];
                    dp[j] = cost1 > cost2 ? cost1 : cost2;
                }
                    // else
                    // dp[j] = dp[j];
                    // do nothing

            }
        }
        return dp[V];
    }
}

class OneZeroPackImpl3 implements OneZeroPack{

    @Override
    public int oneZeroPack(int N, int V, int[] C, int[] W) {
        int[] dp = new int[V + 1];
        Arrays.fill(dp, 0);
        int sigma = 0;
        for(int i = 1; i <= N; i++){
            sigma += W[i - 1];
            for(int j = V; j >= Math.max(j - sigma, C[i - 1]); j--){
                if(C[i - 1] <= j){
                    int cost1 = dp[j];
                    int cost2 = dp[j - C[i - 1]] + W[i - 1];
                    dp[j] = cost1 > cost2 ? cost1 : cost2;
                }
            }
        }
        return dp[V];
    }
}
